AVL 트리

3. 연산 (Operations)

AVL 트리의 읽기 전용 연산(탐색, 순회 등)은 일반적인 이진 탐색 트리와 동일하게 수행된다. 하지만 수정 연산(삽입, 삭제)의 경우, 트리의 균형이 깨질 수 있으므로 회전 연산을 통해 균형을 유지해야 한다.

AVL 트리에서는 데이터를 삽입하거나 삭제할 때마다 모든 노드의 균형 계수를 확인하여 트리의 균형 상태를 점검한다. 균형 계수는 (왼쪽 서브트리의 높이) - (오른쪽 서브트리의 높이)로 정의되며, 이 값이 2 이상 또는 -2 이하인 노드가 존재하면 트리의 재구성이 필요하다. 회전은 균형 계수가 2 이상 또는 -2 이하인 노드 중 가장 잎에 가까운 노드부터 수행한다. 회전 연산에 대한 자세한 내용은 트리 회전 문서를 참고하면 된다.

AVL 트리는 합집합, 교집합, 차집합과 같은 집합 연산을 지원한다.^[13] 이러한 연산은 분할(Split)과 결합(Join)이라는 두 가지 보조 연산을 기반으로 효율적으로 구현될 수 있다.

• 결합(Join) 연산: 두 개의 AVL 트리 과 및 키 가 주어졌을 때, 과 의 모든 요소와 를 포함하는 하나의 트리를 반환한다. 단, 는 의 모든 키보다 크고 의 모든 키보다 작아야 한다.
• 분할(Split) 연산: AVL 트리를 특정 키 를 기준으로 작은 두 개의 트리로 나눈다. 하나는 보다 작은 키를, 다른 하나는 보다 큰 키를 갖는 트리이다.

3. 1. 탐색 (Searching)

3. 2. 순회 (Traversal)

3. 3. 삽입 (Insert)

• 대부분의 경우, "P"와 "P의 높은 쪽 부분 트리의 루트 노드"에 주목하여 한 번 회전을 수행하면, 이러한 노드와 그 자손 노드는 균형 조건을 만족하는 상태가 된다. 이 회전을 단일 회전 또는 1중 회전 등으로 부른다.
• 단일 회전으로 균형이 맞춰지지 않는 경우도 있다.
• P의 왼쪽 부분 트리가 더 높고, P의 왼쪽 자식 노드의 오른쪽 부분 트리가 더 높은 경우 (Left Right Case)
• P의 오른쪽 부분 트리가 더 높고, P의 오른쪽 자식 노드의 왼쪽 부분 트리가 더 높은 경우 (Right Left Case)
• 이 때는 복합 회전 또는 2중 회전 등을 수행하여 해결한다.
• 회전 전 P의 왼쪽 자식 노드를 L, L의 오른쪽 자식 노드를 LR이라고 하면, 먼저 L과 LR로 회전하고, 다음에 P와 새롭게 P의 왼쪽 자식 노드가 된 LR로 회전한다.
• 회전 전 P의 오른쪽 자식 노드를 R, R의 왼쪽 자식 노드를 RL이라고 하면, 먼저 R과 RL로 회전하고, 다음에 P와 새롭게 P의 오른쪽 자식 노드가 된 RL로 회전한다.

• 삽입은 트리의 높이를 1 증가시키는 연산인 반해, 회전은 트리의 높이를 1 감소시키는 연산이므로, 이러한 연산에 의해 해당 부분 트리의 높이가 삽입 전과 같아지기 때문이다.
• 삽입으로 인해 균형 계수가 0이 된 노드가 있다는 것은, 삽입 전에 높이가 1 작았던 쪽의 부분 트리에 삽입했다는 것이므로, 해당 노드를 루트로 하는 부분 트리의 높이는 삽입 전후로 변하지 않아, 모든 노드가 균형 조건을 만족하고 있음을 알 수 있다.

• 삽입으로 인해 균형 계수가 1 또는 -1이 된 노드가 있다는 것은, 삽입 전 해당 노드의 좌우 부분 트리의 높이는 같았지만, 삽입으로 인해 한쪽 부분 트리의 높이가 1 커졌다는 것이며, 해당 노드를 루트로 하는 부분 트리의 높이가 1 커졌으므로, 모든 노드가 균형 조건을 만족하고 있음을 보장할 수 없기 때문이다.

3. 4. 삭제 (Delete)

삭제 과정은 다음과 같다:

1. 삭제할 노드 $d$를 루트 노드부터 검색한다.

2. $d$가 단말 노드(자식이 없는 노드)가 아니라면, 왼쪽 부분 트리에서 가장 큰 값을 가진 노드나 오른쪽 부분 트리에서 가장 작은 값을 가진 노드를 찾아 $d$와 위치를 바꾼다.

3. $d$가 단말 노드가 될 때까지 2번 과정을 반복하여 단말 노드 $d$를 삭제한다.

삭제 후에는 트리의 균형이 깨질 수 있다. 이 경우, 삽입과 마찬가지로 $d$의 부모 노드를 $w$라고 하고, 회전을 통해 균형을 맞춘다. 이때, 삭제된 노드 또는 대체 노드의 자식 트리 높이가 1에서 0으로, 또는 2에서 1로 감소한다.^[1]

삭제 후에는 AVL 트리의 불변성(모든 노드의 균형 인수가 -1, 0, 1 중 하나)을 유지하기 위해 각 조상 노드를 확인하는 "역추적" 과정이 필요하다.^[1] 단일 삭제로 인해 AVL 서브트리의 높이는 최대 1만큼 감소할 수 있으므로, 노드의 임시 균형 인수는 -2에서 +2 사이의 값을 가질 수 있다.^[1] 만약 균형 인수가 ±2가 되면, 해당 서브트리는 불균형 상태가 되므로 회전이 필요하다.^[1]

삭제 시 역추적 과정에서 균형 인수가 ±1이 되면(원래 0이어야 함) 해당 서브트리의 높이는 변경되지 않았음을 의미하므로 역추적을 중단할 수 있다.^[1] 균형 인수가 0이 되면(원래 ±1이어야 함) 서브트리의 높이가 1만큼 감소했음을 의미하므로 역추적을 계속해야 한다.^[1]

삭제에 필요한 시간은 검색에 O(log ''n'') 시간이 걸리고, 루트 노드까지 돌아가는 경로에서 최대 O(log ''n'')번의 역추적(평균 O(1))이 필요하므로, 총 O(log ''n'') 시간이 걸린다.^[1]

AVL 트리의 삭제 연산은 일반적인 이진 탐색 트리와 동일하게 삭제를 수행한 후, 균형 조건이 깨졌는지 확인하고 깨졌다면 회전을 통해 트리를 재구성한다.^[2] 삽입과 마찬가지로, 삭제된 노드의 부모 노드부터 루트 노드 방향으로 경로를 조사하며, 균형 조건이 맞지 않는 노드가 있으면 단일 회전 또는 이중 회전을 수행한다.^[2]

삭제할 노드가 자식 노드를 두 개 가진 경우, 삭제할 노드의 왼쪽 부분 트리에서 가장 큰 값을 가진 노드(또는 오른쪽 부분 트리에서 가장 작은 값을 가진 노드)를 찾아 삭제할 노드와 교체하는 과정이 필요하며, 이때 탐색한 경로도 기억해야 한다.^[2] 노드 삭제는 교체 후에 이루어지므로, 균형 조건 확인도 교체된 노드의 부모 노드부터 시작해야 한다.^[2]

삭제 시 균형 조건 확인 과정에서 균형 계수가 1 또는 -1인 노드를 발견하면, 해당 노드를 루트로 하는 부분 트리의 높이는 삭제 전후로 변하지 않으므로, 모든 노드가 균형 조건을 만족하고 있음이 보장되어 처리를 종료할 수 있다.^[2] 그러나 균형 계수가 0인 노드를 발견하거나 회전을 수행한 경우에는, 해당 부분 트리의 높이가 변경되었을 수 있으므로, 추가적인 확인이 필요할 수 있다.^[2]

3. 5. 회전 (Rotation)

AVL 트리에서 회전은 트리의 균형을 유지하기 위한 중요한 연산이다. 삽입이나 삭제로 인해 트리의 균형이 깨질 수 있는데, 이때 회전을 통해 균형을 회복한다. 회전에는 단일 회전과 이중 회전 두 가지가 있으며, 이들은 모두 O(1) 시간 복잡도를 가진다.^[11]

AVL 트리에서 노드 삽입 및 삭제 시, 일반적인 이진 탐색 트리와 동일한 과정을 거치지만, 높이 균형 성질(height balance property)을 만족하지 않게 될 수 있다. 이때 회전을 통해 트리를 재구성하여 높이 균형 성질을 유지한다.^{[6] [12]}

회전의 기준이 되는 세 노드 x, y, z는 다음과 같이 정의된다.

• z: 삽입/삭제된 노드로부터 루트 노드로 가는 경로 상에서 가장 먼저 나타나는 불균형 노드
• y: z의 자식 중 더 높은 높이를 갖는 노드
• x: y의 자식 중 더 높은 높이를 갖는 노드

회전은 이 세 노드와 그 서브트리들을 재배치하여 균형을 맞추는 작업이다. 구체적인 회전 방법은 단일 회전과 이중 회전에서 설명한다.

3. 5. 1. 단일 회전 (Single Rotation)

''rotate_Left''(''X'',''Z'')]]

;단순 왼쪽 회전의 코드 조각

입력	X = 왼쪽으로 회전될 서브트리의 루트
	Z = X의 오른쪽 자식, Z는 오른쪽으로 무거움
	높이 == X
결과	재균형된 서브트리의 새로운 루트

```c

node *rotate_Left(node *X, node *Z) {

// Z는 형제보다 2만큼 높음

t23 = left_child(Z); // Z의 내부 자식

right_child(X) = t23;

if (t23 != null)

parent(t23) = X;

left_child(Z) = X;

parent(X) = Z;

// 첫 번째 경우, BF(Z) == 0,

// 삭제 시에만 발생하며, 삽입 시에는 발생하지 않음:

if (BF(Z) == 0) { // t23이 t4와 높이가 같았음

BF(X) = +1; // t23이 이제 더 높음

BF(Z) = –1; // t4가 이제 X보다 낮음

} else { // 두 번째 경우는 삽입 또는 삭제 시 발생:

BF(X) = 0;

BF(Z) = 0;

}

return Z; // 회전된 서브트리의 새로운 루트 반환

}

```

일반적인 이진 탐색 트리에서의 삽입은 "왼쪽 자식의 값 ≤ 부모의 값 ≤ 오른쪽 자식의 값"을 만족하는 가지의 말단을 탐색하여, 거기에 새로 생성한 노드를 연결하지만, AVL 트리에서는 균형 조건을 만족하는지 조사하고, 만족하지 않는 경우에는 회전을 수행한다.

삽입 후, "삽입한 노드의 부모 노드"에서 "루트 노드"를 향해 순서대로 조사해 나갈때, 균형 조건을 만족하지 않는 노드(P라고 한다)가 있는 경우, "P"와 "P의 높은 쪽 부분 트리의 루트 노드"에 주목하여 한 번 회전을 수행하면, 이러한 노드와 그 자손 노드는 균형 조건을 만족하는 상태가 된다. 이 회전을 단일 회전 또는 1중 회전 등으로 부른다.

3. 5. 2. 이중 회전 (Double Rotation)

트리의 재구성 작업은 회전(Rotation)이라고 불린다. 이중 회전은 불균형 노드와 그 자식 노드의 방향이 다른 경우(LR, RL)에 수행된다.

$x$가 이진 탐색 트리의 노드이고 $y$가 부모, $z$가 할아버지 노드일 때 다음과 같이 재구성한다.

# $x$, $y$, $z$를 왼쪽-오른쪽 순서 (inorder)로 나열 한 순서대로 $a$, $b$, $c$ 라고 하고, $x$, $y$, $z$의 4개의 부분 트리들을 왼쪽-오른쪽 순서 (inorder)로 나열한 것을 $T\_\{0\}$, $T\_\{1\}$, $T\_\{2\}$, $T\_\{3\}$ 라고 한다.

# $z$가 root인 부분 트리를 $b$를 root로 하는 새로운 부분 트리로 바꾼다.

# $a$가 $b$의 왼쪽 자식이 되고 $T\_\{0\}$, $T\_\{1\}$은 각각 $a$의 왼쪽, 오른쪽 자식이 된다.

# $c$가 $b$의 오른쪽 자식이 되고, $T\_\{2\}$, $T\_\{3\}$는 각각 $c$의 왼쪽, 오른쪽 자식이 된다.

$b=x$ 일 때 $x$를 $y$와 회전시키고 다시 $z$와 회전시키는 것처럼 보인다. 이 작업을 double rotation이라고 한다.

일반적인 이진 탐색 트리에서의 삽입과 달리 AVL 트리는 삽입 후에 균형이 맞지 않을 때 회전을 한다. 단일 회전으로 균형이 맞춰지지 않는 경우는 다음과 같다.

• P의 왼쪽 부분 트리가 더 높고, P의 왼쪽 자식 노드의 오른쪽 부분 트리가 더 높은 경우 (그림의 Left Right Case)
• P의 오른쪽 부분 트리가 더 높고, P의 오른쪽 자식 노드의 왼쪽 부분 트리가 더 높은 경우 (그림의 Right Left Case)

이 경우에는 각각 다음과 같이 두 번 회전을 수행함으로써 해결할 수 있다. 이를 복합 회전 또는 2중 회전 등으로 부른다.

• 회전 전 P의 왼쪽 자식 노드를 L, L의 오른쪽 자식 노드를 LR이라고 하면, 먼저 L과 LR로 회전하고, 다음에 P와 새롭게 P의 왼쪽 자식 노드가 된 LR로 회전한다.
• 회전 전 P의 오른쪽 자식 노드를 R, R의 왼쪽 자식 노드를 RL이라고 하면, 먼저 R과 RL로 회전하고, 다음에 P와 새롭게 P의 오른쪽 자식 노드가 된 RL로 회전한다.

3. 6. 집합 연산 (Set Operations)

AVL 트리는 합집합, 교집합, 차집합과 같은 집합 연산을 지원한다.^[13] 이러한 연산은 분할(Split)과 결합(Join)이라는 두 가지 헬퍼 연산을 기반으로 효율적으로 구현될 수 있다.

• 결합(Join) 연산: 두 개의 AVL 트리 과 및 키 가 주어졌을 때, 과 의 모든 요소와 를 포함하는 하나의 트리를 반환한다. 단, 는 의 모든 키보다 크고 의 모든 키보다 작아야 한다. 이 연산의 비용은 두 입력 트리의 높이 차이에 비례한다.

• 분할(Split) 연산: AVL 트리를 특정 키 를 기준으로 작은 두 개의 트리로 나눈다. 하나는 보다 작은 키를, 다른 하나는 보다 큰 키를 갖는 트리이다. 이 연산의 비용은 이며, 이는 트리의 높이에 해당한다.

이러한 헬퍼 연산들을 사용하여 두 AVL 트리의 합집합, 교집합, 차집합을 구할 수 있다. 예를 들어, 두 AVL 트리 과 의 합집합은 다음과 같이 계산할 수 있다.

1. 를 의 루트 키를 기준으로 분할하여 두 개의 트리 와 를 얻는다.

2. 의 왼쪽 서브트리와 의 합집합, 의 오른쪽 서브트리와 의 합집합을 재귀적으로 계산한다.

3. 2단계에서 얻은 두 합집합과 의 루트를 결합(Join)하여 최종 합집합 트리를 생성한다.

교집합과 차집합 연산도 유사한 방식으로 구현할 수 있다. 이러한 집합 연산들은 재귀 호출이 서로 독립적이므로 병렬 처리가 가능하다.^[13]

합집합, 교집합, 차집합의 복잡도는 크기가 $m$ 및 $n\; \backslash ;\; (\backslash ge\; m)$인 AVL 트리에 대해 $\backslash text\{O\}\backslash left(m\; \backslash log\; \backslash left(\{n\backslash over\; m\}+1\backslash right)\backslash right)$이다. 또한, 이러한 연산은 병렬로 병렬 깊이 $\backslash text\{O\}(\backslash log\; m\backslash log\; n)$로 실행될 수 있다.^[13]

4. 다른 자료 구조와의 비교

AVL 트리와 레드-블랙 트리는 모두 자체 균형 이진 탐색 트리이며, 수학적으로 관련이 있다.^[14] 모든 AVL 트리는 레드-블랙 트리로 칠할 수 있지만, AVL 균형을 이루지 않는 레드-블랙 트리도 존재한다.^[14] AVL 트리는 레드-블랙 트리에 비해 더 엄격하게 균형을 유지하므로, 탐색 성능은 AVL 트리가 더 좋지만 삽입 및 삭제 성능은 레드-블랙 트리가 더 좋을 수 있다.

AVL 트리와 레드-블랙 트리는 회전을 통해 트리의 균형을 유지한다. 최악의 경우, 회전 없이도 AVL 또는 레드-블랙 트리 삽입 또는 삭제는 AVL 균형 인자(또는 레드-블랙 트리의 색상)에 대한 검사 및/또는 업데이트가 필요하다. 레드-블랙 트리의 삽입 및 삭제와 AVL 트리의 삽입은 0개에서 3개의 꼬리 재귀 회전을 필요로 하며 상각된 시간에 실행되므로,^{[15] [16]} 평균적으로도 일정하다. 최악의 경우 회전이 필요한 AVL 삭제도 평균적으로는 이다.

레드-블랙 트리는 각 노드에 1비트의 정보(색상)를 저장해야 하는 반면, AVL 트리는 대부분 균형 인자에 대해 2비트를 사용하지만, 자식에 저장될 때는 «형제보다 낮음»의 의미를 가진 1비트면 충분하다.

크기가 인 트리의 경우, AVL 트리의 높이는 최대 ${\displaystyle h\leqq \;c\log _{2}(n+d)+b< \;c\log _{2}(n+2)+b}$이다. 여기서 ${\displaystyle \varphi :={\tfrac {1+{\sqrt {5}}}{2}}\approx 1.618}$는 황금비, ${\displaystyle c:={\tfrac {1}{\log _{2}\varphi }}\approx 1.440}$, ${\displaystyle b:={\tfrac {c}{2}}\log _{2}5-2\approx \;-0.328}$, ${\displaystyle d:=1+{\tfrac {1}{\varphi ^{4}{\sqrt {5}}}}\approx 1.065}$이다. 반면 레드-블랙 트리의 높이는 최대 ${\displaystyle h\leqq \;2\log _{2}(n+1)}$이다.^[17]

AVL 트리는 레드-블랙 트리보다 더 엄격하게 균형을 이루며, 최대 높이의 점근 관계는 AVL/RB ≈0.720이다. 삽입 및 삭제의 경우, Ben Pfaff는 79개의 측정에서 AVL/RB 관계가 0.677과 1.077 사이이며 중앙값 ≈0.947 및 기하 평균 ≈0.910임을 보여준다.^[4]

5. 응용

AVL 트리는 일반적인 이진 탐색 트리와 달리 데이터 입력 순서에 관계없이 항상 균형 잡힌 트리를 유지하여 탐색 효율을 높인다. 일반적인 이진 탐색 트리는 데이터가 정렬된 상태로 입력되면 트리가 선형 리스트처럼 구성되어 탐색 계산량이 최악의 경우 $O\backslash left(n\backslash right)$이 된다. 반면 AVL 트리는 "어떤 노드의 좌우 서브트리의 높이 차도 1 이하"라는 평형 조건을 항상 만족시켜 탐색 계산량이 항상 $O\backslash left(\backslash log\; n\backslash right)$이다. 이러한 특성으로 AVL 트리는 데이터베이스 시스템, 운영체제, 컴파일러 등 다양한 분야에서 효율적인 자료 구조로 활용되며, 특히 탐색 연산이 빈번한 환경에서 뛰어난 성능을 제공한다.

참조

_[1] 웹사이트 AVL Trees http://pages.cs.wisc[...]
_[2] 논문 An algorithm for the organization of information https://zhjwpku.com/[...]
_[3] 서적 Algorithms Addison-Wesley
_[4] 웹사이트 Performance Analysis of BSTs in System Software http://www.stanford.[...] Stanford University 2004-06
_[5] 웹사이트 AVL trees are not weight-balanced? (meaning: AVL trees are not μ-balanced?) https://cs.stackexch[...]
_[6] 서적 Sorting and searching Addison-Wesley
_[7] 문서 However, the balance information can be kept in the child nodes as one bit indicating whether the parent is higher by 1 or by 2; thereby higher by 2 cannot occur for both children. This way the AVL tree is a [[WAVL tree|"rank balanced" tree]], as coined by [[#Haeupler|Haeupler, Sen and Tarjan]].
_[8] 서적 Mastering data structures through 'C' language University Science Press, an imprint of Laxmi Publications Pvt. Ltd.
_[9] 서적 Advanced data structures Cambridge University Press 2008
_[10] 서적 Schaum's outline of theory and problems of data structures with Java https://archive.org/[...] McGraw-Hill 2000
_[11] 서적 Data structures and algorithm analysis in C++ Pearson Addison-Wesley 2006
_[12] 서적 An Introduction to Binary Search Trees and Balanced Trees Free Software Foundation, Inc. 2004
_[13] 간행물 Symposium on Parallel Algorithms and Architectures ACM
_[14] 웹사이트 AVL tree https://xlinux.nist.[...] National Institute of Standards and Technology 2016-07-02
_[15] 서적 Algorithms and Data Structures http://link.springer[...] Springer Berlin Heidelberg 2008
_[16] 서적 Handbook of Data Structures and Applications https://www.taylorfr[...] Chapman and Hall/CRC 2017-12-15
_[17] 문서 Red–black tree#Proof of bounds
_[18] 웹인용 AVL Trees http://pages.cs.wisc[...]